package org.example.myleet.p854;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    static class Situation {
        String s;
        int pos;

        public Situation(String s, int pos) {
            this.s = s;
            this.pos = pos;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Situation{");
            sb.append("s='").append(s).append('\'');
            sb.append(", pos=").append(pos);
            sb.append('}');
            return sb.toString();
        }
    }

    public int kSimilarity(String s1, String s2) {
        if (s1.equals(s2)) {
            return 0;
        }
        HashSet<String> sSet = new HashSet<>();
        Queue<Situation> queue = new LinkedList<>();
        queue.add(new Situation(s1, 0));
        sSet.add(s1);
        int k = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                Situation situation = queue.poll();
                if (s2.equals(situation.s)) {
                    return k;
                }
                char[] sChar = situation.s.toCharArray();
                int i = situation.pos;
                while (i < sChar.length && sChar[i] == s2.charAt(i)) {
                    ++i;
                }
                for (int j = i + 1; j < sChar.length; ++j) {
                    if (sChar[j] != s2.charAt(j) && sChar[j] == s2.charAt(i)) {
                        char t = sChar[j];
                        sChar[j] = sChar[i];
                        sChar[i] = t;
                        String newS = new String(sChar);
                        if (!sSet.contains(newS)) {
                            queue.add(new Situation(newS, i + 1));
                            sSet.add(newS);
                        }
                        t = sChar[j];
                        sChar[j] = sChar[i];
                        sChar[i] = t;
                    }
                }
                --size;
            }
            ++k;
        }
        return k;
    }
}
